Introduction

لو حابب تشوف نفس الملخص بتجربة افضل اضغط هنا

Definitions

Algorithm: is a method or a process adopted in order to solve a problem.
Problem: task to be performed, consist of inputs and outputs.
Program: Is an instance of algorithm in a certain programming language.
Algorithm Analysis: The process of evaluating the efficiency of an algorithm in terms of time and space complexity. It helps in determining the performance of an algorithm.

Find

represents the time complexity function of an algorithm. It describes the amount of time an algorithm takes to run as a function of the input size .

Simple fast way to find

Statements: Order of 1 int n = 5;
Conditions: choose the max if(n && log(n)) => O(n)
Loops: Order of body number of iterations
constants are removed.
the biggest order is the dominant
This method doesn't work in all cases .. so we need another method

Summation-equation method to find

Examples:

for(int i = 1; i <= n; i++)
	print i;

// or

for(int i = n; i >= 1; i--)
	print i;

for(int i = 1; i <= n; i*=2)
	print i;

// or 

for(int i = n; i >= 1; i/=2)
	print i;

for(int i = 1; i <= n; i++)
	for(int j = 1; j <= n; j++)
		print i;

for(int i = 1; i <= n; i*=3)
	for(int j = 1; j <= n; j++)
		print i;

for(int i = 1; i <= n; i*=3)
	for(int j = 1; j <= n; j*=3)
		print i;

for(int i = 1; i <= n; i++)
	for(int j = i + 1; j <= n; j++)
		print i;

Asympotitic Notations, oh, omegam, theta

Asymptotic notations describe the growth rate of an algorithm's running time as the input size approaches infinity. They help us compare algorithms based on their efficiency, ignoring constant factors and lower-order terms.

means: الحد صاحب أكبر أس في المعادلة

1. Big-O Notation

Represents the worst-case / upper-bound of an algorithm.
It tells us the maximum time an algorithm can take for large .
Formally, if there exist constants and such that:

Example: If , then: and

2. Omega Notation

Represents the best-case / lower-bound of an algorithm.
It tells us the minimum time an algorithm will take.
Formally, if there exist constants and such that:

Example: If , then:

3. Theta Notation

Represents the average-case / tight-bound (both upper and lower).
It tells us that an algorithm runs in exactly a certain order of time.
Formally, if there exist constants and such that:

Example: If , then:

Relationship Between

If , then it equals both and .
If = , then

Examples:

How to find and for and

For

Write down all the constants (with thier signs) multiplied with .
To find make the two sides equal and solve for n.

For

Write down with its constant.
To find make the two sides equal and solve for n.

Different type of questions

$Pasted image 20250402213534.png$

Pasted image 20250402213152.png

Little oh and little omega

زيها زي الO والاوميجا العاديين بس مفيهاش كلمة يساوي
Pasted image 20250402213851.png
Pasted image 20250402214059.png

Important method

if you're asked is

put it in this form
if it is

Example 1

Example 2

Groth Rate

Groth Rate VS Time

الـ Groth rate عكس ال time

Pasted image 20250402214551.png

Recursion Equation

Any recursive function has time in the following format:

Examples:

int fact(int n){
	if(n == 0) return 0;
	else return fact(n - 1);
}

// or 

int fact(int n){
	if(n == 0) return 0;
	else return n * fact(n - 1);
}

الـ n دي مجرد رقم ثابت بينضرب في ناتج الفانكشن مبيأثرش فالوقت

int fact(int n){
	if(n == 0) return 0;
	else return fact(n/2);
}

int fact(int n){
	if(n == 0) return 0;
	else return fact(n/2) + fact(n/2);
}

int fact(int n){
	if(n == 0) return 0;
	else return fact(n/2) + fact(3n/2);
}

int fact(int n){
	if(n == 0){
		for(int i = 1; i <= n; i++) {
			cout << i;
		}
		return 1;
	}
	else return fact(n - 1) + fact(n - 2);
}

Master method to solve recurrence

بتحل بعض انواع ال Recursion مش بيشتغل غير على المعادلات اللي بالشكل التالي
نبدأ نقارن كالتالي:

Examples:

Pasted image 20250402230346.png Pasted image 20250402230359.png

Another formula

if they're not equal we can't use this method.

Pasted image 20250402224416.png

Advanced Problem

VS--CourseAlgorithmAnalysisDesignCourseFromAtoZArabicUdemy-12’26”.jpg

Tree method to solve recurrence

The recursion tree method is a visual way to analyze recurrence relations by expanding them level by level and summing up the work done at each level. This helps us find the overall complexity of an algorithm.

Steps in the Tree Method

Expand the recurrence tree level by level.
Find the number of nodes and the work done at each level.
Sum up the work done across all levels.
Determine the height of the tree and compute the final sum.

Example 1: Simple Recurrence

Each call to makes two recursive calls to , and at each level, the extra work is .

Pasted image 20250402234857.png

بما إن كل مره بنقسم على 2 وهنوصل لـ 0 فالاخر فا الـ height =
انما لو كنا بنطرح 1 او رقم ثابت فا ال hight =

Summing the work done at each level:

Dealing with Geometric Serieses

كل عنصر بيساوي اللي قبله مضروب في ثابت

Examples

Pasted image 20250403001519.png
Pasted image 20250403001343.png

Dealing with Arithmatic Serieses

كل عنصر بيساوي اللي قبله مجموع عليه ثابت, هنحاول نحطها على شكل قانون ال sum

Pasted image 20250403001735.png
Pasted image 20250403153222.png

Substitution method to solve recurrence

The substitution method is a powerful technique for solving recurrence relations by:

Guessing a solution (using intuition or pattern recognition).
Proving the guess using mathematical induction.

Steps in the Substitution Method

Guess the solution using pattern expansion or intuition.
Use induction to prove that the guess holds.
Solve for constants if necessary.

Example 1: Solve

Step 1: Expand the Recurrence

Expanding the recurrence for a few levels:
After expansions:

Step 2: Identify Base Case

The recursion stops when , meaning , so: .

Step 3: Compute the Total Work

The summation simplifies:
Final Answer:

Example 2:

Step 1: Expand the Recurrence

Expanding for a few values:

Continuing this process, after steps:

Step 2: Find the Base Case

If we assume the base case is , then setting gives:

Step 3: Compute the Final Expression

Substituting :
Since , we get:
Final Answer:

Space Complexity

Space complexity measures the total memory used by an algorithm as a function of the input size .

هنا هنحسب عادي ولكن هنهتم فقط بالسطور اللي بخزن فيها داتا فالميموري, كمثال

int x = 5; // 1
int y = 7 // 2
int z = x + y; // 3
cout << z;
// Total = O(1)

الموضوع بسيط ولكن فيه شوية تريكات فال recursive functions

Memory Stack

مكان فالميموري بيخزن الfunction والstatic variables شغال بمبدأ الـLast in first out
شرح تفصيلي فالفيديو الخاص بالدكتور اضغط هنا

Each recursive call adds a new function frame to the call stack, increasing space usage. For a recurrence like:

Auxiliary Space vs. Total Space

Auxiliary Space: Extra memory used excluding input storage.
Total Space: Input storage + Auxiliary space.

Examples:

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) { // 1
        cout << arr[i] << " ";
    }
}

void recursiveFunc(int n) {
    if (n == 0) return;
    recursiveFunc(n - 1);
}

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

The recursive Fibonacci function makes two calls, but they are not executed simultaneously. The recursion first fully evaluates before calling .

Linear Search

The algorithm checks each element in an array one by one.

int linearSearch(int arr[], int n, int target) {
    // Loop through each element of the array
    for (int i = 0; i < n; i++) {
        // Check if the current element matches the target
        if (arr[i] == target) {
            return i;  // Return the index if found
        }
    }
    return -1;  // Return -1 if the target is not found
}

Time Complexity

Worst-Case Time Complexity:
In the worst case (if the target is not present or is at the very end), the algorithm makes comparisons.
Average-Case Time Complexity:
On average, it might inspect about half the elements before finding the target, but in Big-O notation, this still simplifies to .
Best-Case Time Complexity:
If the target is the first element, it will be found in time.

Space Complexity

Binary Search

Binary search is an efficient algorithm for finding a target element in a sorted array.

it works by repeatedly dividing the search interval in half. If the target value is less than the value in the middle of the interval, the algorithm continues on the lower half. Otherwise, it continues on the upper half. This process repeats until the target is found or the search interval is empty.

int binarySearchRecursive(int arr[], int low, int high, int target) {
    if (low > high) 
        return -1;
    
    int mid = (high + mid) / 2;  

    if (arr[mid] == target) 
        return mid;  

    if (arr[mid] < target)  
    return binarySearchRecursive(arr, mid + 1, high, target);
    return binarySearchRecursive(arr, low, mid - 1, target);  
}

Time Complexity:

Worst-case / Average-case: , because the search space is halved each time.
Best-case: , if the target is the middle element in the first iteration.

Space Complexity

Insertion Sort

Insertion Sort is a simple and efficient sorting algorithm.
It builds the sorted sequence one element at a time by picking the next element and placing it in its correct position within the already sorted part.

How Insertion Sort Works

Start from the second element (index 1) because a single element (index 0) is already sorted.
Pick the next element and compare it with the elements before it.
Shift elements to the right to make space for the picked element.
Insert the picked element in its correct position.
Repeat the process for all elements.

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > key){
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Time Complexity

Best Case (Already Sorted):
Worst Case (Reverse Sorted):
Average Case:

Space Complexity

Properties

in place -> reorders the elements in the same array.
stable -> elements with same values remain in the same order.

Selection Sort

Selection Sort is a simple comparison-based sorting algorithm. The idea is to repeatedly select the minimum (or maximum) element from the unsorted part of the array and move it to the correct sorted position.

Steps

Start from index 0.
Find the minimum element from arr[i] to arr[n-1].
Swap that minimum element with arr[i].
Move to the next index (i + 1) and repeat until the array is sorted.

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[minIdx]) minIdx = j;
        swap(arr[i], arr[minIdx]);
    }
}

Time Complexity

Best Case (Already Sorted):
Worst Case (Reverse Sorted):
Average Case:

Space Complexity

Properties

in place -> reorders the elements in the same array.
not stable -> elements with same values dont't remain in the same order.
- can be converted into stable by shifting elements instead of swapping

Quick Sort

Quick Sort follows the Divide and Conquer strategy:

Pick a "pivot" element.
Partition the array so that:
- All elements less than the pivot go to the left.
- All elements greater than the pivot go to the right.
Recursively apply the same logic to the left and right subarrays.

Code

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high], i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
			i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Time Complexity

Best Case (Already Sorted):
Worst Case (Reverse Sorted):
Average Case:

Space Complexity

Properties

in place -> reorders the elements in the same array.
not stable -> elements with same values don't remain in the same order.

Merge Sort

Merge Sort is a Divide and Conquer algorithm:

Divide the array into two halves.
Recursively sort each half.
Merge the sorted halves into a single sorted array.

Code

void merge(vector<int>& arr, int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2)
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}
void mergeSort(vector<int>& arr, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

Time Complexity

Best Case (Already Sorted):
Worst Case (Reverse Sorted):
Average Case:

Space Complexity

Properties

out of place -> reorders the elements in other arrays.
stable -> elements with same values remain in the same order.

Count Sort

Counting Sort is a non-comparison sorting algorithm ideal for sorting integers within a known, limited range.
Instead of comparing elements, it:

Counts how many times each value occurs.
Uses these counts to determine the positions of each element in the sorted output.

void countSort(vector<int>& arr) {
    int max_val = *max_element(arr.begin(), arr.end());

    // Step 1: Create and initialize count array
    vector<int> count(max_val + 1, 0);

    // Step 2: Store count of each element
    for (int num : arr)
        count[num]++;

    // Step 3: rebuild the sorted array
    int k = 0;
    for (int i = 0; i <= max_val; i++) {
        for (int j = 0; j < count[i]; j++){
            arr[k++] = i;
        }
    }
}

Time Complexity

Best Case (Already Sorted):
Worst Case (Reverse Sorted):
Average Case:
: range of input.

Space Complexity

Properties

out of place -> reorders the elements in other arrays.
stable -> elements with same values remain in the same order.

Comparison

Searching algorithms

Algorithm	Time Complexity (Best / Avg / Worst)	Space	In-Place	Stable	Notes
Linear Search	/ /		✅	✅	Works on unsorted data
Binary Search	/ /		✅	✅	Requires sorted data

Sorting algorithms

Algorithm	Time Complexity (Best / Avg / Worst)	In-Place	Stable	Notes
Selection Sort	/ /	✅	❌	Simple, always
Insertion Sort	/ /	✅	✅	Fast on nearly sorted arrays
Quick Sort	/ / $²$	✅	❌	Fast in practice, not stable
Merge Sort	/ /	❌	✅	Very predictable, uses extra space
Count Sort	/ /	❌	✅	Only for integers / small range

Algorithm Desing Techniques

Algorithm design techniques are systematic approaches to solving computational problems efficiently.
يعني لما يجيلك سؤال أو مشكلة في البرمجة، مش لازم تبدأ تحل كده من دماغك وخلاص… لأ، فيه طرق معينة، كل طريقة ليها طريقة تفكير بتخليك توصل لحل سريع ومنظّم.

Brute Force

هو أسهل وأبسط طريقة لحل أي مشكلة… بتجرّب كل الحلول الممكنة لحد ما تلاقي الصح

Characteristics:

Straightforward and direct approach
Explores all possible solutions
Often serves as a baseline for comparison يعني تعمله الأول وبعدين تطوّر خوارزمية أحسن وتشوف الفرق
Generally simple to implement سهل فالكتابة
Usually inefficient for large inputs مش عملي مع الداتا اللي حجمها كبير

When to use:

Problem size is small
No obvious optimized algorithm exists
Quick implementation is required
For algorithm verification

تستخدمه لو حجم المشكلة عندك صغير ومفيهاش عناصر كتير، او لو مفيش حل افضل واسرع من ده، او لو عايز تكتب الكود بتاعه بسرعه، او لو عندك حل تاني بطريقة تانية وعايز تتاكد انه صح فا بتستخدم البروت فورس عشان تقارن بين الناتج بتاع الالجورذم التانية وبين الناتج بتاعه

Limitations:

Exponential or factorial time complexity for many problems
Impractical for large inputs

الtime complexity بتبقى غالبا سيئة جدا جدا

Divide and Conquer

Characteristics:

Breaks problem into smaller, similar subproblems
Solves subproblems recursively
Combines solutions to solve the original problem

Key steps:

Divide: Break the problem into smaller subproblems
Conquer: Solve subproblems recursively
Combine: Merge solutions of subproblems

When to use:

Problems with recursive structure
When subproblems are independent <- مهم
For parallelizable computations

Advantages:

Often yields efficient algorithms
Amenable to parallel processing

تنفع تتنفذ بشكل متوازي، أو ممكن نوزّع شغلها على أكتر من معالج/كور (CPU cores) في نفس الوقت.

Natural for recursive problems

معناها إنك لما تواجه مشكلة كبيرة، بدل ما تحلها مرة واحدة، تقسمها لمشاكل أصغر (دي مرحلة الـ "Divide")، وتحل كل واحدة لوحدها غالبًا باستخدام Recursion (دي مرحلة الـ "Conquer")، وبعد كده تدمج نتايج الحلول الصغيرة دي مع بعض علشان تطلع حل المشكلة الأصلية (ودي مرحلة الـ "Combine"). الطريقة دي ممتازة لو المشكلة ممكن تتقسم وأجزاءها مش متداخلة، وبيكون فيها كفاءة عالية خاصة في المسائل اللي ينفع نحلها بشكل متوازي. أمثلة معروفة زي Merge Sort وBinary Search بيعتمدوا على نفس الفكرة دي

Greedy Algorithms

Characteristics:

Makes locally optimal choices at each step
Hopes that these choices lead to a globally optimal solution
Never reconsiders previous choices

Key components:

Optimal substructure: An optimal solution contains optimal solutions to subproblems
Greedy choice property: A globally optimal solution can be found by making locally optimal choices

When to use:

Problems where local optimum leads to global optimum
When you can prove the greedy approach is correct

Limitations:

Does not work for all problems
May not find the global optimum

هي طريقة حل بتشتغل خطوة بخطوة، وفي كل خطوة بتختار أحسن حل ظاهر قدامك دلوقتي، على أمل إن الاختيارات دي كلها في الآخر توصلنا لأفضل حل نهائي. الميزة إنها سريعة وبسيطة، بس العيب إنها مش بترجع تصلّح نفسها، يعني لو أخدت قرار غلط خلاص بتكمل عليه علشان كده مش بتنفع مع كل المشاكل، إلا لو المشكلة فيها خاصيتين مهمين، أولًا إن الحل النهائي بيتكوّن من حلول مثالية لأجزاء صغيرة (دي بنسميها optimal substructure)، وثانيا إن الحل الأمثل النهائي ممكن نوصله عن طريق اختيارات مثالية محلية (greedy choice property)

Dynamic Programming

Characteristics:

Breaks down problem into overlapping subproblems
Stores results of subproblems to avoid redundant calculations
Builds solution bottom-up or top-down (memoization)

Key components:

Optimal substructure
Overlapping subproblems

ال Overlapping Subproblems يعني وانت بتحل المشكلة بتلاقي إن في نفس الجزء بيتحسب أكتر من مرة والمشكلة فيها تكرار لحسابات حصلت قبل كده، وممكن نخزّن النتايج دي بدل ما نحسبها تاني ونبقى نستخدمها لما نحتاجها بعدين

When to use:

Problems with overlapping subproblems
When recursive solutions have exponential complexity
Optimization problems requiring optimal solution

Approaches:

Top-down (Memoization): Recursive approach with caching
Bottom-up (Tabulation): Iterative approach building from smallest subproblems

هي طريقة لحل مشاكل بتتكرر فيها نفس الخطوات كذا مرة، فبدل ما نعيد الحساب كل شوية، بنحسب الحاجة مرة واحدة ونخزّن النتيجة (دي فكرة "الذاكرة"). الطريقة دي بتشتغل كويس في المشاكل اللي فيها subproblems بتتكرر، فيه طريقتين نحل بيهم: يا إما Top-down (وده بالـ Recursion + Memoization، يعني بننزل للمشكلة الصغيرة ونرجع بالنتايج)، أو Bottom-up (وده بنبدأ من أصغر مشكلة ونطلع لفوق خطوة خطوة في جدول)

الDP بيبقى مفيد جدًا لما يكون الحل العادي (زي الـ Recursion) بياخد وقت كبير جدًا، زي في مشاكل الـ Fibonacci، knapsack، وlongest common subsequence

Example Fibonacci Numbers

Calculate the Fibonacci number, where , and for

Brute Force Approach (Recursive)

int fib(int n) {
	if(n == 0 || n == 1) return n;
	return fib(n-1) + fib(n-2);
}

Directly implement the recursive definition
No optimization, recalculate values even if previously computed
Time Complexity: - Exponential due to redundant calculations
Space Complexity: - Maximum depth of recursion stack

Divide and Conquer Approach

For Fibonacci, a pure divide and conquer approach would be similar to the brute force recursive solution.
However, we can use matrix exponentiation which is a more efficient divide and conquer strategy.

Use the mathematical property that Fibonacci numbers can be computed using matrix exponentiation
Divide the problem of calculating the power into smaller powers
Apply the divide and conquer approach to matrix exponentiation
Time Complexity: - Due to the efficiency of the divide and conquer approach for exponentiation
Space Complexity: - Due to recursion stack

Greedy Approach

The Fibonacci sequence doesn't naturally lend itself to a greedy approach since:

There's no locally optimal choice to make at each step
The problem requires knowing previous values rather than making independent choices
A simple iterative calculation is often labeled as "greedy" but is more accurately just an iterative approach.

int fib(int n) {
	if(n == 0 || n == 1) return n;

	int a = 0, b = 1, temp;
	for (int i = 2; i <= n; i++) {
		temp = a + b;
		a = b;
		b = temp;
	}
	return temp;
}

Start with the base values
Iteratively compute the next Fibonacci number using the previous two
Only store the two most recent values
Time Complexity: - We perform n-1 iterations
Space Complexity: - We only store two variables regardless of input size

Dynamic Programming Approach

Top-down with Memoization

Use recursion with memoization (caching)
Store computed Fibonacci values to avoid redundant calculations

int arr[n + 1]; // -> initilize by -1 

int fib(int n) {
	if(n == 0 || n == 1) return n;

	if(arr[n] != -1) return arr[i];
	arr[n] = fib(n-1) + fib(n-2);
	return arr[n];
}

Before computing a value, check if it's already calculated
Store each calculated value for future use
Time Complexity: - Each Fibonacci number is calculated exactly once
Space Complexity: - For the memoization table plus recursion stack

Bottom-up with Tabulation

Build a table of Fibonacci numbers from the bottom up
Use previously computed values to calculate new ones

int fib(int n) {
	int dp[n + 1];
	dp[0] = 0;
	dp[1] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i-1] + dp[i-2];
	}
	return arr[n];
}

Start from the base cases and iteratively build up the solution
Time Complexity: - We compute each Fibonacci number once
Space Complexity: - For the DP table

Space-Optimized Dynamic Programming

نفس ال iterative فوق، بس ده في حالة الfibonacci بس

for Fibonacci Problem

Pasted image 20250616112327.png

The choice of algorithm design technique

depends on the specific problem characteristics:

Brute Force: Simple problems or when other techniques don't provide significant advantages.
Divide and Conquer: Problems that can be broken into independent subproblems and combined.
Greedy: Problems where local optimal choices lead to global optimal solution.
Dynamic Programming: Problems with overlapping subproblems and optimal substructure.